This invention is in the field of communications, and is more specifically directed to the encoding and decoding of digital information in such communications.
High-speed data communication services, for example in providing high-speed Internet access, have become a widespread utility for many businesses, schools, and homes. In its current stage of development, this access is provided by an array of technologies. Recent advances in wireless communications technology have enabled localized wireless network connectivity according to the IEEE 802.11 standard to become popular for connecting computer workstations and portable computers to a local area network (LAN), and typically through the LAN to the Internet. Broadband wireless data communication technologies, for example those technologies referred to as “WiMAX” and “WiBro”, and those technologies according to the IEEE 802.16d/e standards, have also been developed to provide wireless DSL-like connectivity in the Metro Area Network (MAN) and Wide Area Network (WAN) context.
Multiple-input-multiple-output (MIMO) communication techniques have recently attracted attention, especially in the wireless LAN context. In a general sense, MIMO communications are realized by providing multiple signal paths (i.e., RF data path, or “chain”, and antenna) both at a transmitter and at a receiver. In this manner, the transmitted information is either redundantly or independently transmitted over multiple spatial streams between a transmitter antenna and a receiver antenna. The spatial diversity provided by the MIMO approach provides either improved data rate or improved bit error rate in the signal, after combining of the multiple spatial streams at the receiver. These improvements are attractive in any wireless communications context, including wireless LAN (or MAN or WAN) technology, and wireless telephony. An overview of MIMO technology is provided in Gesbert et al., “From Theory to Practice: An Overview of MIMO Space-Time Coded Wireless Systems”, Journal on Selected Areas in Communications, Vol. 21, No. 3 (IEEE, April 2003), pp. 281-302.
In the wireless LAN context, MIMO communication technology is being investigated for use in conjunction with orthogonal frequency-division multiplexing (OFDM) techniques. As known in the art, OFDM refers to a broadband communications approach in which modulated signals are transmitted over multiple narrow-bandwidth (e.g., 20 kHz) channels. Standardization efforts for use of MIMO OFDM wireless LAN communications have been ongoing in the industry, specifically with reference to the IEEE 802.11n standard. It is contemplated that wireless LAN communications under the eventual 802.11n standard will be able to reach 250 Mbit/second data rates, at distances of up to 50 meters.
A problem that is common to all data communications technologies, including of course MIMO OFDM communications, is the corruption of data by noise. As is fundamental in the art, the signal-to-noise ratio for a communications channel is a degree of goodness of the communications carried out over that channel, as it conveys the relative strength of the signal that carries the data (as attenuated over distance and time), to the noise present on that channel. These factors relate directly to the likelihood that a data bit or symbol as received differs from the data bit or symbol as transmitted. This likelihood of a data error is reflected by the error probability for the communications over the channel, commonly expressed as the Bit Error Rate (BER) ratio of errored bits to total bits transmitted. In short, the likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful.
Error detection and correction techniques are typically implemented by the technique of redundant coding. In general, redundant coding inserts data bits into the transmitted data stream that do not add any additional information, but that indicate, on decoding, whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream even if errors are present.
Many types of redundant codes that provide error correction have been developed. One type of code simply repeats the transmission, for example by sending the payload followed by two repetitions of the payload, so that the receiver deduces the transmitted data by applying a decoder that determines the majority vote of the three transmissions for each bit. Of course, this simple redundant approach does not necessarily correct every error, but greatly reduces the payload data rate. In this example, a predictable likelihood exists that two of three bits are in error, resulting in an erroneous majority vote despite the useful data rate having been reduced to one-third. More efficient approaches, such as Hamming codes, have been developed toward the goal of reducing the error rate while maximizing the data rate.
The well-known Shannon limit provides a theoretical bound on the optimization of decoder error as a function of data rate. The Shannon limit provides a metric against which codes can be compared, both in the absolute and relative to one another. Since the time of the Shannon proof, modem data correction codes have been developed to more closely approach the theoretical limit. An important class of these conventional codes includes “turbo” codes, which encode the data stream by applying two convolutional encoders. One of these convolutional encoders encodes the datastream as given, while the other encodes a pseudo-randomly interleaved version of the data stream. The results from the two encoders are interwoven to produce the encoded data stream.
Another class of known redundant codes are the Low Density Parity Check (LDPC) codes. The fundamental paper describing these codes is Gallager, Low-Density Parity-Check Codes, (MIT Press, 1963), monograph available at http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/. In these codes, a sparse matrix H defines the code, with the encodings c of the payload data satisfying:Hc=0  (1)over Galois field GF(2). Each encoding c consists of the source message ci combined with the corresponding parity check bits cp for that source message ci. The encodings c are transmitted, with the receiving network element receiving a signal vector r=c+n, n being the noise added by the channel. Because the decoder at the receiver also knows matrix H, it can compute a vector z=Hr. However, because r=c+n, and because Hc=0:z=Hr=Hc+Hn=Hn  (2)The decoding process thus involves finding the most sparse vector x that satisfies:Hx=z  (3)over GF(2). This vector x becomes the best guess for noise vector n, which can be subtracted from the received signal vector r to recover encodings c, from which the original source message ci is recoverable.
There are many known implementations of LDPC codes. Some of these LDPC codes have been described as providing code performance that approaches the Shannon limit, as described in MacKay et al., “Comparison of Constructions of Irregular Gallager Codes”, Trans. Comm., Vol. 47, No. 10 (IEEE, October 1999), pp. 1449-54, and in Tanner et al., “A Class of Group-Structured LDPC Codes”, ISTCA-2001 Proc. (Ambleside, England, 2001).
In theory, the encoding of data words according to an LDPC code is straightforward. Given enough memory or small enough data words, one can store all possible code words in a lookup table, and look up the code word in the table according to the data word to be transmitted. But modem data words to be encoded are on the order of 1 kbits and larger, rendering lookup tables prohibitively large and cumbersome. Accordingly, algorithms have been developed that derive codewords, in real time, from the data words to be transmitted. A straightforward approach for generating a codeword is to consider the n-bit codeword vector c in its systematic form, having a data or information portion ci and an m-bit parity portion cp such that c=(ci|cp). Similarly, parity matrix H is placed into a systematic form Hsys, preferably in a lower triangular form for the m parity bits. In this conventional encoder, the information portion ci is filled with n-m information bits, and the m parity bits are derived by back-substitution with the systematic parity matrix Hsys. This approach is described in Richardson and Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Trans. on Information Theory, Vol. 47, No. 2 (February 2001), pp. 638-656. This article indicates that, through matrix manipulation, the encoding of LDPC codewords can be accomplished in a number of operations that approaches a linear relationship with the size n of the codewords. However, the computational efficiency in this and other conventional LDPC encoding techniques does not necessarily translate into an efficient encoder hardware architecture. Specifically, these and other conventional encoder architectures are inefficient because they typically involve the storing of inverse matrices, by way of which the parity check of equation (1), or a corollary, is solved in the encoding operation.
By way of further background, copending patent application Ser. No. 10/329,597, filed Dec. 26, 2002, now published as U.S. Patent Application Publication No. US 2004/0034828, and copending patent application Ser. No. 10/806,879, filed Mar. 23, 2004, and now published as U.S. Patent Application Publication No. US 2004/0194007 A1, both commonly assigned herewith and incorporated herein by this reference, describe a family of structured irregular LDPC codes, and decoding architectures for those codes. The quasi-cyclic structure of this family of LDPC codes can also provide efficiencies in the hardware implementation of the encoder, as described in copending patent application Ser. No. 10/724,280, filed Nov. 28, 2003, now published as U.S. Patent Application Publication No. US 2004/0148560 A1, commonly assigned herewith and incorporated herein by this reference. The encoder and encoding method that are described in U.S. Patent Application Publication No. US 2004/0148560 A1 follow a generalized approach, and are capable of handling such complications as row rank deficiency.
By way of still further background, copending patent application Ser. No. 11/201,391, filed Aug. 10, 2005 and published as U.S. Patent Application Publication No. US 2006/0036926, commonly assigned herewith and incorporated herein by this reference, describes constraints on this family of structured irregular LDPC codes that enable recursive, and efficient, encoding of communications.
By way of still further background, copending patent application Ser. No. 11/284,929, filed Nov. 22, 2005 and published as U.S. Patent Application Publication No. US 2006/0123277 A1, commonly assigned herewith and incorporated herein by this reference, describes the shortening and puncturing of systematic codewords, and more specifically describes the selection of the number of shortened bits and the number of punctured bits from a given codeword length and code rate, for encoding according to a different selected codeword length. The approach described in this U.S. Patent Application Publication No. US 2006/0123277 A1 is believed to be particularly useful in connection with broadband wireless MAN communications according to the IEEE 802.16 standard.
By way of still further background, it is known to restructure a codeword arrangement in response to a comparison of the fraction of information bits that are to be shortened to the fraction of parity bits that are to be punctured.
As fundamental in the art of coded communications, the codeword length greatly affects the efficiency and performance of the communications system. As such, it is desirable to optimize communications by wisely selecting these code parameters. However, in the context of MIMO OFDM communications, many factors in the particular system implementation and operation are present that ought to be taken into account in selecting the optimum codeword length. These factors include the number of transmit antennae (and RF chains), the number of receive antennae (and RF chains), the number of OFDM subchannels, packet lengths, whether space-time block coding (“STBC”) will be used to transmit a single spatial stream across multiple antennae, the modulation scheme applied to individual OFDM subchannels (e.g., 16-QAM, 64-QAM), the desired code rate, whether a short guard interval option is used, and the like.
Convolutional error correcting codes can be readily and flexibly adapted to a wide range of codeword lengths and code rates. It is desirable to obtain the important benefits provided by LDPC codes; however, LDPC codes operate on fixed block sizes, and as such are not easily adapted to varying selections of codeword length and code rate. As discussed above, and as described in the above-incorporated U.S. Patent Application Publication No. US 2006/0123277 A1, it is also desirable to have a minimum number of codeword lengths and code rates in modern LDPC transceivers, so that the memory and computational requirements can be kept modest.
By way of further background, copending patent application Ser. No. 11/465,020, filed Aug. 16, 2006, commonly assigned herewith and incorporated herein by this reference, describes transceiver circuitry for use in a multiple-input, multiple-output (MIMO), orthogonal frequency-division multiplexing (OFDM), communications environment. The codeword length and codeword arrangement for LDPC coding in that environment are selected by determining a minimum number of OFDM symbol periods required for a payload size, and the number of available information bits in those symbol periods. A rule-based approach is used to select the codeword length, and the number of codewords required to send the packet. Shortening is then applied to the code, followed by determining whether puncturing or repeating of bits is necessary to efficiently use the available OFDM symbols.
Once the structure of the LDPC code is determined, whether through use of the methods described in the above-incorporated copending application Ser. No. 11/465,020 or otherwise, one must still select the particular code to be used that fits that structure. The performance of error correcting codes, including LDPC codes, is typically measured by reference to bit error rate over a range of signal-to-noise ratio, usually with the noise characterized as AWGN (additive white Gaussian noise). It has been observed, in connection with this invention, that the code performance of an ensemble of LDPC codes of the same codeword size and code rate can vary widely, even if the structure of the code is common among the codes.
Techniques for evaluating and selecting candidate codes are known. Kang et al., “Flexible Construction of Irregular Partitioned Permutation LDPC Codes with Low Error Floors”, Communication Letters, Vol. 9, No. 6 (IEEE, June 2005), pp. 534-36, describes the selection of LDPC codes by avoiding small “stopping sets” in the Tanner graph of LDPC codes. In this context, a “stopping set” is a set of input nodes whose associated check sum nodes (or “neighbors”) are each connected to the input nodes in this set by at least two arcs. “Cycles” in the Tanner graph of a code are sequences of connections among nodes that return to the starting node without repeating an edge. It is known that the existence of small “stopping sets”, or the existence of small “cycles”, in the Tanner graph of a given code are harmful to the error floor performance of that code. The Kang et al. letter describes an approach to selecting LDPC codes, by selecting codes that do not have closed paths below a threshold length (e.g., no closed paths of length four), and that have relatively low numbers of cycles of shorter lengths above that threshold. Zhang et al., “VLSI Implementation-Oriented (3,k)-Regular Low-Density Parity-Check Codes”, IEEE Workshop on Signal Processing Systems (September 2001), pp. 25-36, describes a somewhat similar approach, referring to a “girth average”, in which the length of the shortest cycle passing through each node is averaged over the total number of nodes for the code; this girth average is determined over an ensemble of codes to select candidate codes, which are then analyzed for their simulated error rates.
FIG. 8 illustrates a part of a Tanner graph for a belief propagation code, of which LDPC codes constitute a subset. In the example of FIG. 8, four input nodes N1 through N4 and four sums S1 through S4 are shown. Many more input nodes and sums may, of course, be present, as suggested in FIG. 8. In this example, nodes N1 and N2 each contribute to sum S1 and also to sum S2. Node N1 also contributes to sum S3, node N2 also contributes to sum S4, node N3 contributes to sum S2, and so on. FIG. 8 illustrates an example of a closed path, or cycle, of length four. This closed path can be seen by following the arrowed connectors shown in FIG. 8, in sequence. The path from node N1 to sum S1 is a first leg, followed by the path from sum S1 to node N2, then from node N2 to sum S2, and back from sum S2 to node N1. This closed path is a “cycle”, because the sequence ends at the same node at which it started (i.e., node N1), and no path was traveled twice. As mentioned above relative to the Kang et al. and Zhang et al. references, it is known in the art that the presence of cycles of short length in the Tanner diagram of an LDPC is typically reflected in poor error rate performance. This poor performance is believed to result from poor diversity in the contributions of distant nodes in sums—the error correcting properties of the code tend to be improved if the contributions to checksums are widely spread among the input nodes. For example, as noted above, LDPC codes having one or more cycles of length four are often excluded from use.
It has been discovered, in connection with this invention, that analysis of cycles in the Tanner graph of LDPC codes does not necessarily result in a determination of the optimum code in an ensemble of codes with the same structure, code rate, and codeword size.